10999. Кребс

Кребс – это игра, в которой следует из квадратных пластин с написанными на них буквами складывать слова. Составлять можно только слова, которые присутствуют в словаре. Каждая пластина кроме буквы содержит также количество очков, которое дается игроку при ее использовании в слове. Цена сложенного слова равна сумме очков пластин, из которых оно сложено. Процесс игры состоит в том, что игроку дают определенный набор пластин, из которых он должен сложить одно слово с наибольшей ценой. В задаче следует по заданному словарю и набору пластин составить слово с наибольшей ценой.

Вход. Первая строка содержит количество слов n (1 £ n £ 100000) в словаре. Следующие n строк описывают имеющийся словарь. Следующая строка содержит количество игр m (1 £ m £ 1000), которое следует сыграть. Каждая игра состоит из количества имеющихся на руках пластин p (1 £ p £ 10) , за которым идут p строк, описывающих пластины игрока в формате: <буква> <количество очков>. Буквы являются прописными, количество очков у каждой буквы не меньше 0 и не больше 10.

Выход. Для каждой игры вывести слово с наибольшей ценой, которое можно сложить из имеющихся пластин.

Пример входа

2

abcd

hgfe

1

10

a 1

b 2

c 3

d 4

e 5

f 6

g 7

h 8

i 9

j 10

Пример выхода

26

РЕШЕНИЕ

структуры данных + перебор

Анализ алгоритма

Словарь для всех игр одинаковый, хранить будем его в структуре “множество” set<string>. Перед запоминанием слова отсортируем его буквы. Поскольку количество пластин у игрока в каждой игре не более 10, то полным перебором генерируем все слова, которые он может составить (все подмножества из имеющихся букв на пластинах), проверяем, принадлежит ли это слово словарю, и если да – то ищем среди всех таких слов то, которое имеет наибольшую цену.

Реализация алгоритма

В переменной s храним все слова словаря. Символьный массив bufer используем при чтении строк, буквы игрока храним в массиве letter, а их соответствующие значения в массиве v.

set<string> s;

char bufer[50], letter[11];

int v[11];

Читаем словарь, состоящий из n слов. Слова читаем в символьный массив bufer, преобразовываем их в тип string, сортируем буквы и заносим в множество s.

scanf("%d\n",&n);

for(i = 0; i < n; i++)

{

gets(bufer); s_temp = (string)bufer;

sort(s_temp.begin(),s_temp.end());

s.insert(s_temp);

}

Читаем количество игр m.

scanf("%d",&m);

while(m--)

{

Читаем набор пластин игрока. Игрок имеет пластин, буквы заносим в массив letter, а соостветствующие им очки – в целочисленный массив v.

scanf("%d\n",&p);

for(i = 0; i < p; i++)

scanf("%c %d\n",&letter[i],&v[i]);

В переменной res будем искать наибольшую цену слова. Все подмножества из p пластин (кроме пустого) генерируем перебирая значения i от 1 до 2^p – 1 . Если j - ый бит числа i равен 1, то j - ую пластину включаем в текущее подмножество. Сортируем буквы полученного подмножества, хранящегося в строке s_temp. В переменной Sum хранится его цена. Ищем слово s_temp в словаре при помощи метода find класса string. Если слово найдено и его цена больше текущей, хранящейся в переменной res, то полагаем res = Sum. Перебрав все подмножества (все возможные слова, которые можно составить из имеющихся пластин), выводим значение переменной res.

res = 0;

for(i = 1; i < (1 << p); i++)

{

Sum = 0; s_temp = "";

for(j = 0; j < p; j++)

if (i & (1 << j)) Sum += v[j],s_temp += letter[j];

sort(s_temp.begin(),s_temp.end());

if ((s.find(s_temp) != s.end()) && (Sum > res)) res = Sum;

}

printf("%d\n",res);

}